package cn.yuemouren.heap.maxheap;

import cn.yuemouren.array.Array;

/**
 * @Author: Timi
 * @Description: 最大堆
 * @Date: 2020/6/29 9:27
 */
public class MaxHeap<T extends Comparable<T>> {

    private Array<T> heap;

    public MaxHeap() {
        heap = new Array<>();
    }

    public MaxHeap(int capacity){
        heap = new Array<>(capacity);
    }

    public MaxHeap(T[] array) {
        this.heap = new Array<>(array);
        heapify();
    }

    public int getSize(){
        return heap.getSize();
    }

    public boolean isEmpty(){
        return heap.isEmpty();
    }

    /**
     * 向堆中添加元素
     * @param t
     */
    public void add(T t){
        heap.addLast(t);
        siftUp(heap.getSize()-1);
    }

    /**
     * 取出堆中最大元素
     * @return
     */
    public T extractMax(){
        T result = heap.get(0);
        heap.swap(0,heap.getSize()-1);
        heap.removeLast();
        siftDown(0);
        return result;
    }

    public T getMax(){
        return heap.get(0);
    }

    /**
     * 新插入值替换最大值
     * @param t
     * @return
     */
    public T replace(T t){
        T res = extractMax();
        heap.set(0,t);
        siftDown(0);
        return res;
    }

    private void heapify() {
        for (int i = getParentIndex(heap.getSize()-1); i >= 0; i--){
            siftDown(i);
        }
    }

    private void siftUp(int k) {
        while(k > 0 && heap.get(k).compareTo(heap.get(getParentIndex(k))) > 0){
            heap.swap(k,getParentIndex(k));
            k = getParentIndex(k);
        }
    }

    private void siftDown(int i) {
        while(getLeftChildIndex(i) < heap.getSize()){
            //存放左右孩子中值最大的那个索引
            int j = getLeftChildIndex(i);
            if(getRightChildIndex(i) < heap.getSize() &&
                    heap.get(getLeftChildIndex(i)).compareTo(heap.get(getRightChildIndex(i))) < 0){
                j = getRightChildIndex(i);
            }
            if(heap.get(i).compareTo(heap.get(j)) > 0)
                return;
            heap.swap(i,j);
            i = j;
        }
    }

    //获取父节点索引
    private int getParentIndex(int index){
        if(index == 0){
            throw new IllegalArgumentException("root is not parent!");
        }
        return (index - 1) / 2;
    }

    //获取左孩子节点
    private int getLeftChildIndex(int index){
        return index * 2 + 1;
    }

    //获取右孩子节点
    private int getRightChildIndex(int index){
        return index * 2 + 2;
    }
}
